package hot_100;

import java.util.HashMap;

public class 随机链表的复制 {
    public static void main(String[] args) {

    }

    HashMap<Node, Node> map = new HashMap();

    //其他方法
    public Node copyRandomList(Node head) {
        if (head == null)
            return null;
        if (!map.containsKey(head)) {
            Node temp = new Node(head.val);
            map.put(head, temp);
            temp.next = copyRandomList(head.next);
            temp.random = copyRandomList(head.random);
        }
        return map.get(head);
    }

//  我的方法
//    public Node copyRandomList(Node head) {
//        HashMap<Node, Integer> map = new HashMap<>();
//        HashMap<Integer, Node> map2 = new HashMap<>();
//        Node temp = head;
//        for (int i = 0; temp != null; i++) {
//            map.put(temp, i);
//            temp = temp.next;
//        }
//        Node ans = new Node(0);
//        Node head2 = ans;
//        temp = head;
//        for (int i = 0; temp != null; i++) {
//            Node t = new Node(temp.val);
//            map2.put(i, t);
//            head2.next = t;
//            head2 = t;
//            temp = temp.next;
//        }
//        temp = head;
//        head2 = ans.next;
//        while (temp != null) {
//            if (temp.random != null) {
//                head2.random = map2.get(map.get(temp.random));
//            }
//            head2 = head2.next;
//            temp = temp.next;
//        }
//        return ans.next;
//    }

    class Node {
        int val;
        Node next;
        Node random;

        public Node(int val) {
            this.val = val;
            this.next = null;
            this.random = null;
        }
    }
}
